#pragma once
#include <vector>
#include <algorithm>
template <typename T, typename Compare = std::less<T>>
class Heap {
public:
	Heap() = default;
	Heap(const std::vector<T>& nums) :_nums(nums) {
		for (int i = (_nums.size() - 2) / 2; i >= 0; --i) {
			AdjustDown(i);
		}
	}
	void Push(const T& val) {
		_nums.emplace_back(val);
		AdjustUp(_nums.size() - 1);
	}
	T Top() {
		return _nums[0];
	}
private:
	bool AdjustDown(int parent) {
		if (parent < 0 || parent >= _nums.size()) {
			return false;
		}
		int child = parent * 2 + 1;
		while (child < _nums.size()) {
			if (child + 1 < _nums.size() && _cmp(_nums[child], _nums[child + 1])) {
				++child;
			}
			if (!_cmp(_nums[parent], _nums[child])) {
				break;
			}
			std::swap(_nums[parent], _nums[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		return true;
	}
	bool AdjustUp(int pos) {
		if (pos < 0 || pos >= _nums.size()) {
			return false;
		}
		int parent = (pos - 1) / 2;
		while (pos > 0 && _nums.size() > 1) {
			if (!_cmp(_nums[pos], _nums[parent])) {
				std::swap(_nums[pos], _nums[parent]);
				pos = parent;
				parent = (pos - 1) / 2;
			} else {
				break;
			}
		}
		return true;
	}
private:
	std::vector<T> _nums;
	Compare _cmp;
};
